import java.util.*;

public class test {
    // leetcode 738.单调递增的数字
    public int monotoneIncreasingDigits(int n) {
        if(n < 10) return n;
        String s = String.valueOf(n);
        char[] arr = s.toCharArray();
        int len = arr.length;
        int begin = -1;
        int temp = 0;
        for(int i = 1;i < len;i++){
            temp = i;
            if(begin == -1 && arr[i - 1] > arr[i]){
                begin = i;
            }
            while(begin == -1 && i < len && arr[i - 1] == arr[i]){
                if(i != len - 1 && arr[i] > arr[i + 1]){
                    begin = temp;
                }
                i++;
            }
        }
        if(begin == -1) return n;
        arr[begin - 1]--;
        if(arr[begin - 1] == 0){
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i < len - 1;i++){
                sb.append(9);
            }
            return Integer.valueOf(sb.toString());
        }else {
            StringBuilder sb = new StringBuilder();
            for(int i = begin;i < len;i++){
                arr[i] = '9';
            }
            for(int i = 0;i < len;i++){
                sb.append(arr[i]);
            }
            return Integer.valueOf(sb.toString());
        }
    }
    // leetcode 134.加油站
    // 1. 暴力枚举 -> O(n^2)
    public int canCompleteCircuit1(int[] gas, int[] cost) {
        int n = gas.length;
        int num = 0;
        int index = 0;
        for(int i = 0;i < n;i++){
            num = gas[i];
            index = i + 1;
            if(index == n) index = 0;
            for(int j = 0;j < n;j++){
                if(index == n) index = 0;
                // 记录到达下一地点要花费的油
                num -= cost[index - 1 >= 0 ? index - 1 : n - 1];
                if(num < 0) break;
                // 记录到达下一地点获得的油
                if(index != i) num += gas[index];
                index++;
            }
            if(num >= 0) return i;
        }
        return -1;
    }
    // 2. 贪心优化 -> O(n)
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int[] number = new int[n];
        // 得到净利润
        for(int i = 0;i < n;i++){
            number[i] = gas[i] - cost[i];
        }
        int num = 0;
        int index = 0;
        for(int i = 0;i < n;i++){
            if(number[i] < 0) continue;
            num = 0;
            index = i;
            for(int j = 0;j < n;j++) {
                num += number[index];
                if(num < 0) break;
                index++;
                if(index == n) index = 0;
            }
            // 因为以i为起点能够到达这里,就代表i位置净利润为正数
            // 如果(i~index)总和<0,那么(i+1~index)总和也必定<0
            // 因此舍弃掉(i+1~index-1)为起点,直接以index作为下次起点
            if(num < 0 && i < index) i = index;
            if(num >= 0) return i;
        }
        return -1;
    }
    // leetcode 991.坏了的计算器
    // 正难则反
    public static int brokenCalc(int startValue, int target) {
        if(target == 1) return startValue - target;
        int sum = 0;
        while(target != startValue){
            if(target % 2 == 0 && target > startValue){
                target /= 2;
                sum++;
            }else if(target <= startValue){
                sum += startValue - target;
                return sum;
            }else {
                target++;
                sum++;
            }
        }
        return sum;
    }
}
